#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * 递归法
 */
class Solution1{
private:
	int getNum(TreeNode* node){
		if(node == nullptr) return 0;
		int leftNum = getNum(node->left);
		int rightNum = getNum(node->right);
		int total = 1 + leftNum + rightNum;
		return total;
	}
public:
	int countNodes(TreeNode* root) {
		queue<TreeNode*> que;
		int result = 0;
		if(root != nullptr) que.push(root);
		while(!que.empty()){
			int size = que.size();
			result += size;
			while(size--){
				TreeNode* node = que.front();que.pop();
				if(node->left) que.push(node->left);
				if(node->right) que.push(node->right);
			}
		}
		return result;
	}
};

/**
 * 层次遍历
 */
class Solution2{
public:
	int countNodes(TreeNode* root) {
		queue<TreeNode*> que;
		int result = 0;
		if(root != nullptr) que.push(root);
		while(!que.empty()){
			int size = que.size();
			result += size;
			while(size--){
				TreeNode* node = que.front();que.pop();
				if(node->left) que.push(node->left);
				if(node->right) que.push(node->right);
			}
		}
		return result;
	}
};

/**
 * 使用完全二叉树的性质
 */
class Solution3{
public:
	int countNodes(TreeNode* root){
		if(root==nullptr) return 0;
		TreeNode* leftNode = root->left;
		TreeNode* rightNode = root->right;
		int leftDepth = 0,rightDepth = 0;
		while(leftNode){
			leftNode = leftNode->left;
			leftDepth++;
		}
		while(rightNode){
			rightNode = rightNode->right;
			rightDepth++;
		}
		if(leftDepth == rightDepth){
			return (2 << leftDepth) - 1;
		}
		return countNodes(root->left) + countNodes(root->right) + 1;
	}
};
int main(){
	
	return 0;
}
